In recent years, concurrent/parallel programming in which different computer programs execute simultaneously and access shared memory has become quite popular. Concurrently executing programs that operate within the context of a single computer program are commonly referred to as threads of a multi-threaded program. Multi-threaded programming has inherent challenges both because of the simultaneous nature of the execution of the threads and because the different threads of the program have access to shared memory. As a result of the simultaneous executions of the threads, operations performed by the threads do not necessarily occur in any particular order. However, there are instances in which proper operation of the multi-threaded program requires that one or more of the operations performed in one or more threads be performed in a specific order relative to the operations of one or more other threads. For example, two or more threads that access the same memory location may rely on a specific value or values being present in the shared memory location when that shared memory location is accessed. However, the specific value or values in the shared memory location when that memory location is accessed by any given thread may depend on the order in which one or more of the threads access the shared memory location. Further, ensuring the order in which a shared memory location is accessed by any given thread in a multi-threaded program is very difficult to control given the simultaneous operation of the various threads.
Programmers often use compound statements and mutually exclusive locks to properly order the operations performed in one thread with respect to the operations performed in another thread. This process of ordering the operations is referred to as serialization. However, the locks and compound statements must be placed in any given thread or threads in a position(s) that causes the desired order of operations to be performed. When these locks and/or compound statements are not properly placed, the desired order of operations is not achieved and a concurrency violation may result thereby causing a computer crash, an incorrect program output or other undesirable outcome(s).
Fixing any computer error, or bug, including those caused by a concurrency violation generally involves reproducing the bug so that the bug can be properly identified and so that the responsible portions of the program can be modified to correct the bug. Debugging in the context of a serial program is fairly straightforward as it involves sequentially stepping through the instructions of the code until the bug occurs and then revising the instructions responsible for the bug. However, this method of debugging does not work well in a multi-threaded program because the order in which the instructions of the various threads of a multi-threaded program are executed is unknown and, indeed, may vary during any given execution of the program. In fact, a particular bug present in a multi-threaded program may not occur upon every execution of the program (i.e., the bug may be non-deterministic).